package pers.qianyu.month_202012.date_20201208;

import java.util.*;

/**
 * 787. K 站中转内最便宜的航班
 * https://leetcode-cn.com/problems/cheapest-flights-within-k-stops/
 *
 * @author mizzle rain
 * @date 2020-12-08 14:24
 */
public class FindCheapestPrice {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        // dp[i][k] 表示经过 k 站中转，到达 i 的最小费用
        int[][] dp = new int[n][K + 1];
        for (int[] ints : dp) {
            Arrays.fill(ints, Integer.MAX_VALUE);
        }
        // 初始化 不需要中转直接到达的情况
        for (int[] flight : flights) {
            if (flight[0] == src) {
                dp[flight[1]][0] = flight[2];
            }
        }
        // 目的地等于 src ，那么费用为 0
        for (int i = 0; i < K + 1; i++) {
            dp[src][i] = 0;
        }
        for (int i = src; i <= dst; i++) {
            for (int[] flight : flights) {
                if (flight[0] == src && flight[1] == i) {
                    dp[i][0] = flight[2];
                }
            }
        }
        for (int i = 1; i < K + 1; i++) {
            for (int[] flight : flights) {
                if (dp[flight[0]][i - 1] != Integer.MAX_VALUE) {
                    dp[flight[1]][i] = Math.min(dp[flight[1]][i],
                            dp[flight[0]][i - 1] + flight[2]);
                }
            }
        }
        return dp[dst][K] == Integer.MAX_VALUE ? -1 : dp[dst][K];
    }
}
